Evacuation planning is a critical aspect that involves movement of people away from threat or actual occurrence of hazard such as natural disasters, terrorist attacks, fires and bombs. Safe evacuation of a large number of people in a timely manner is a major challenge for building administrators.
There have been several endeavors in this domain to provide methods for planning evacuation paths. Linear Programming (LP) based polynomial time techniques for evacuation problem uses time-expanded graphs for the network, where the expression for time complexity makes it non-scalable even for mid-sized networks. Capacity Constrained Route Planner (CCRP) techniques use generalized shortest path technique to find shortest paths from any source to any sink, provided that there is enough capacity available on all nodes and edges of the path. Space complexity and unnecessary expansion of source nodes in each iteration are two main disadvantages of CCRP. CCRP++ runs faster than CCRP but the quality of solution is not good, because availability along a path may change between the times when paths are reserved and when they are actually used.
Network flow based approaches are based on minimum cost transshipment and earliest arrival transshipment. The minimum cost approach does not consider the distances between evacuees and exits. It may fail if there are exits very far away. Problems also arise if a lot of exits share the same bottleneck edges. The earliest arrival approach uses an optimal flow over time and thus does not suffer from these problems. But the exit assignment computed by the earliest arrival approach may not be optimal.
There is a need therefore for methods and systems that address the above and other possible drawbacks and limitations of the currently used methods and systems for planning evacuation paths.